1. Field of the Invention
The present invention relates generally to a decoding circuit for a code which is variable of length per bit. More specifically, the invention relates to a decoding circuit which can unitedly process a plurality of bits and can variably designate number of bits to be processed.
2. Description of the Related Art
It has been known that a compression coding can be realized by employing variable-length code with providing shorter codes for signals having high frequencies of occurrences and longer codes for signals having low frequencies of occurrences. Such a manner of encoding is called as entropy coding. It should be noted that Huffman coding is a kind of entropy coding. Such entropy coding has been employed in various applications, such as for encoding of a voice signal, a video signal and so forth. In case, a time-series signal encoded employing the entropy coding and thus having inclination of frequencies of occurrences of codes is to be decoded, there are generally two known types of decoding circuits, in the prior art. The first type is a decoding system, in which the variable length code is received per bit in serial manner and the decoding is performed with discrimination employing a binary tree. The second type is a decoding system, in which the variable length code is unitedly processed with decoding the code and the code length simultaneously. Hereinafter further discussed will be given for the first and second types of systems with reference to the accompanying drawings.
FIGS. 14(A) and 14(B) respectively illustrate a variable length code table and a state transition by the binary tree for detailed discussion of the conventional first type decoding circuit. As shown in FIG. 14(A), the shown variable length code table defines a variable length or non-equal length code having code lengths depending upon frequencies of occurrences. The left column shows definitions of the codes and the right column shows meaning (positive integer in the shown case) of the codes. On the other hand, as shown in FIG. 14(B), the state transition by the binary tree provides decoding procedure for performing decoding of the codes per each bit from the left side. Namely, the circles in FIG. 14(B) represent initial state and intermediate state in decoding procedure. Upon initiation of decoding, process is started from the leftmost circle. If the initial bit in decoding is "0", the process branches to a branch (arrow) of "0" and to a branch of "1" otherwise. By repeating such transition for each bit, decoding is completed when a figure is reached.
FIG. 15 shows a conventional variable length decoding table. The decoding table of FIG. 15 illustrates an example realizing the binary tree transition diagram shown in FIG. 14(B) in a form of a table. In the shown table, the right column shows a bit representing intermediate state and completed state of decoding. In the table, "0" represents the decoding completed state and "1" represents the decoding incomplete state. The left column includes addresses of next table entries in case of the decoding incomplete state and the decoded meaning (positive integers in the shown case) in case of the decoding completed state. Decoding process is started at a start address "100000". Then, reference is made to the address "100000" if the leading bit of the code is "0", and to the address "100001" if the leading bit of the code is "1". For example, in case of the address "100001", since the right column is "1" to represents the decoding incomplete state and the left column is "100100" representing that the next address to access is the address "100100". Therefore, from the content of in the address "100001" of the shown table, it can be judged that decoding has to be continued with accessing the address "100100". At the address "100100", since the right column is "0" to represent the decoding completed state and the left column has a content value "000001". Form this, the results of decoding as positive integer "1" can be obtained.
As can be appreciated from the example set forth above, in relation to the number of codes k (k=13 in the shown case), a sum of the decoding incomplete state and the initial state, namely number of cycles in FIG. 14 becomes k-1. This principle may be easily understood by imaging a tournament games. In this case, each code is considered as an entrant and each circle in FIG. 14(B) is considered as a game. As can be appreciated, in such case, the number of games becomes number of entrant minus one. On the other hand, in the example of FIG. 15, since no table entry corresponding to the initial state is present, total number of entries becomes 2k-2=24. As can be appreciated herefrom, the size of the table is merely in the extent proportional to the number of codes.
FIGS. 16(A) and 16(B) are respectively a block diagram of a decoding circuit according to the first decoding system and a chart showing the structure of the variable length decoding table. As shown in FIG. 16(A), the decoding circuit includes a start address register 161 for storing a start address, an end address register 162 for storing an end data, a variable length decoding table 163 constituted of 12 bits.times.2K words, a data register 164 storing data read out from the variable length decoding table, a multiplexer (MPX) 165 for selecting one of respective 12 bits from the registers 161 and 164, an address register 166, a shift register 167, a shift control circuit 169 for controlling the shift register 167 and a decoding timing sequencer 170 for supplying a timing signal for respective components. As shown in FIG. 16(B), the variable length decoding table 163 is constituted of 11 bits of an upper address for continuing retrieval and 1 bit of a retrieval continuation designating portion. The 1 bit of retrieval continuation designating portion represents termination by "0" and continuation by "1". It should be noted that this structure is based on FIG. 15.
FIG. 17 is an operational timing chart of respective portions in FIG. 16(A). Here, the operational timing control is assumed to be performed by the decoding timing sequencer 170 and illustrated mainly in the operations of the data register 164, the shift register 167 and the address register 166.
The operation will be discussed hereinafter with reference to FIGS. 16(A), 16(B) and 17. It should be noted that the above-mentioned decoding timing sequencer 170 is a circuit for generating a timing signal associated with initiation, execution and termination of decoding, in concrete.
At first, 12 bits of an initial address is set in the start address register 161. This initial address passes the multiplexer 165. Then, the least significant bit of the initial address is replaced with a leading bit of the shift register 167 where data to be decoded is stored. Thereafter, the initial address is set in the address register 166. The content of the address register 166 is used for accessing the variable length decoding table 163. Data read out from the variable length decoding table 163 by assessing thereto is stored in the data register 164. At the same time, the shift register 167 is shifted for 1 bit toward left in FIG. 16(A). Next, the content of the data register 164 passes the multiplexer 165. The least significant bit of the content of the data register 164 past through the multiplexer is replaced with the leading bit of the shift register 167, in which data to be subsequently decoded is stored, and is set in the address register 166. The content of the address register 166 is again used for accessing the variable length decoding table 163. The foregoing sequence is repeated until "end" is judged, namely, completion of decoding of one code is recognized. In this example, the repeating unit corresponds one period of a reference clock as illustrated in FIG. 15.
On the other hand, information indicating whether retrieval is "completed" is written in the least significant bit of the variable length decoding table 163 (see FIG. 14(B)). This bit is read out as the least significant bit of the data register 164. The result is transmitted to the shift control circuit 169 and the decoding timing sequencer 170 past through the multiplexer 165. The shift control circuit 169 is the circuit for determining a shifting magnitude of the shift register 167 and serves for preventing shifting operation after completion of retrieval. Once retrieval is completed, data obtained as the result of table retrieval is stored in the end data register 162. The bit length of the variable length decoding table 163 is determined by the length of the end data and the address length necessary as the address of the table per se. The depth of the table is proportional to the number of code to be decoded, as set forth above.
Such first decoding system can make the circuit construction relatively simple by performing a process of 1 bit per 1 clock. However, it is not possible to realize the process performance of 2 or more bits per 1 clock.
FIG. 18 is a block diagram of the decoding circuit on the basis of the conventional second decoding circuit system. The circuit shown in FIG. 18 is so-called a shift comparison type decoding circuit. The decoding circuit includes a data register 182, a shift register 187, a shift control circuit 189, a decoding timing sequencer 190, a variable length decoding table 196, a code length table 197. The variable length decoding table 196 is constituted of 10 bits.times.128 words, and the code length table 197 is constituted of 3 bits.times.128 words.
Similarly to the foregoing first decoding circuit, in the shown decoding circuit, the decoding timing sequencer generates a timing signal associated with initiation, execution and termination of decoding. In conjunction with initiation of decoding, a plurality of bits of the shift register 187 are input to both of the variable length decoding table 196 and the code length table 197. It should be noted that these two tables may be composed into a single table. The variable length decoding table 196 recognizes the code contained in the input sequence and outputs corresponding data to the data register 182. On the other hand, the code length table 197 outputs a length of the code contained in the input sequence, namely, the shifting magnitude of the shift register 187 for the next shifting, to the shift control circuit 189. Therefore, in response to the next clock, shifting over number of bits corresponding to the code length is taken place in the shift register.
On the other hand, bit length of the decoding table 196 depends on the data length, and the bit length of the code length table 197 is determined by number of bits required for expressing the maximum code length with a binary number. The depth of these tables becomes 2.sup.i assuming the maximum code length is i. Normally, in the variable length code, the number of code k frequently becomes much smaller than 2.sup.i. Therefore, the table becomes substantially long. Such second decoding system may achieve speeding of the circuit by performing decoding for one code per one clock. However, since the size of the table is proportional to the exponential function of the maximum code length to cause substantial increase of the memory capacity.
FIG. 19 shows a definition of the conventional variable length code. As shown in FIG. 19, such variable length code includes three data field. Namely, a field 1 represents row number, a field 2 represents data to be encoded and a field 3 represents a variable length code as a result of encoding. Here, as can be appreciated from the field 3, 114 data are encoded into 2 bit to 16 bit variable codes. Hereinafter, discussion will be given for the decoding circuit according to the first decoding system with respect to the variable length code set forth above.
FIG. 20 is a block diagram showing another example of the decoding circuit according to the foregoing first decoding system. As shown in FIG. 20, the decoding circuit comprises a decoding table memory 202, a decoding control sequencer 203, a decoded result data register 204, a shift register 206, a decoding start address register 209, a decoding table memory address register 210 and a multiplexer 218. On the other hand, the decoding table memory 202 is constituted of 17 bits.times.4K words.
FIG. 21 shows an Example of the decoding table to perform decoding. In the shown decoding table, the right column shows a bit indicative of the intermediate state or the completed state of decoding (0: completed, 1: incomplete state). The left column includes addresses of next table entries in case of the decoding incomplete state and the decoded meaning (positive integers in the shown case) in case of the decoding completed state. Decoding process is started at a start address "100000". Then, reference is made to the address "100000" if the leading bit of the code is "0", and to the address "100001" if the leading bit of the code is "1". For example, in case of the address "100001", since the right column is "1" to represents the decoding incomplete state and the left column is "100100" representing that the next address to access is the address "100100". Therefore, from the content of in the address " 100001" of the shown table, it can be judged that decoding has to be continued with accessing the address "100100". At the address "100100", since the right column is "0" to represent the decoding completed state and the left column has a content value "000001". Form this, the results of decoding as positive integer "1" can be obtained.
Next, returning to FIG. 20, the operation of such decoding circuit will be discussed. It should be noted that the timing control for the operation discussed later is performed by the decoding timing sequencer 203. Namely, the decoding timing sequencer 203 generates timing signal associated with initiation, execution and termination of decoding. At first, the initial address is set in the initial address register 209. Then, the initial address passes the multiplexer 218 and its least significant bit is transmitted to the decoding sequencer 203. This is for performing judgement for completion of decoding. Furthermore, this least significant bit is replaced with the leading bit of the shift register 206 and set in the address register 210. In conjunction therewith, the shift register 206 shifts for 1 bit toward left.
After initiation of decoding, control is performed by the decoding sequencer 203 such that the newly accessed content of the decoding table memory 202 passes the multiplexer 218. The subsequent processes are the same as those set out above.
The foregoing sequence is repeated until a judgement "decoding is completed" is made. Once, retrieval is completed, data obtained as a result of retrieval of the decoding table is stored in the end data register 204. Thus, the first decoding system can be constructed with a relatively simple circuit construction by performing process for one bit per one clock similarly to the foregoing example. However, this cannot achieve the processing performance of two or more bits per one clock.
The above-mentioned first decoding system (FIGS. 16(A) and 16(B)) cannot realize the decoding performance of two or more bits per one clock. Therefore, this system encounters a defect in that it is difficult to apply for high speed decoding of the bit sequence. For example, in case of the decoding circuit constructed with typical CMOS LSI, it is difficult under current technology to apply for decoding of the bit sequence of 10 Mb/s or more.
On the other hand, in the above-mentioned conventional second decoding circuit (FIG. 18), for the maximum code length i, number of entry in the code length table becomes 2.sup.i so that large memory capacity is required for decoding one variable length code. This may creates a problem of the area in consideration of designing of the decoding circuit as an integrated circuit. For instance, when i exceeds 16, the capacity of the table exceeds 64 Kwords. It the table size become greater than this, it should be defective for integrating. Namely, such type of memory has high redundancy as requiring writing of the identical content to a large number of entries. It may be possible to attempt logical optimization employing PLA (Programmable Logic Array) or so forth. However, even in such case, in consideration of sequential decoding of a plurality of variable length codes and appropriating of the hardware for a plurality of application, it becomes necessary to provide a plurality of PLA or to re-design the PLA adapting to each application to make design complicate. In addition, in view of the code having extraordinary maximum code length, the application of this system may cause difficulty not only in the code length table but in realization of the shift register.
Furthermore, the above-mentioned other example of the conventional first decoding system (FIG. 20), the decoding process performance of two or more bits per one clock cannot be realized. Namely, in decoding of the variable length code containing code having the maximum code length 16, 16 clock cycle is required in the worst case. Therefore, it causes difficulty in high speed decoding for the bit sequence. For example, in case of the decoding circuit constructed with typical CMOS LSI, it is difficult under current technology to apply for decoding of the bit sequence of 50 Mb/s or more.